An ordered list (interchangeably referred-to herein as an “ordered set”) is a fundamental data structure in computing (sometimes also referred to in computing as an “array” or “vector” or “sequence”). In use, various types of changes can be made to an ordered set of values: a value in the set can be changed, a new value can be inserted into the set, a value can be removed from the set, two values in the set can be exchanged for each other, or an existing value in the set can be moved to another position.
In various computer environments, copies of ordered sets are often maintained in separate locations for different reasons, so it is often necessary to make sure that when changes are made to one instance of the ordered set, before some other instance of the list can be used, that other instance must be made consistent with the changed original (i.e., data coherency among them is maintained).
For example, in a client-server architecture environment, it is not unusual for an ordered set to be stored on, or within storage at, the server, and a copy of that ordered set to be transferred or maintained at a client computer. When changes are made to the ordered set at the client computer, those changes typically need to also be reflected in the ordered set at the server to ensure coherency between the two.
Likewise, for high availability purposes, some document oriented databases may have multiple replicas that must be kept synchronized.
Additionally, change management systems that maintain multiple versions of data in the form of ordered sets, to avoid maintaining multiple copies of the data, typically store only an initial state of data (e.g., version 1) and they store change “differences” for subsequent versions and, when a particular version of the data is required, they must apply those differences sequentially to the initial state (e.g., version 1) to construct the requested version.
In all such cases, maintaining coherency among the ordered sets requires transfers of whatever information is needed to ensure data consistency. Since the ordered sets can be quite large, such transfers of the entire ordered set or even all of the changes (also referred to as “deltas” or “diffs”) can consume significant bandwidth (whether communicated over a network, a computer's internal bus, or some other communication path) and, in some cases, adversely affect processing capability by occupying processing time that could otherwise be used by the computer system for other purposes. In some cases, the communication bandwidth consumption and/or loss of processing capability can even adversely affect other parts of the computer system that have nothing to do with the ordered sets or their associated programs by temporarily “blocking” other activity, for example, by maintaining control of a communication path or causing other processing activity to have to “wait” for completion of some task.
Thus, there is an ongoing technological problem involving the amount of communication bandwidth and/or processing capability/storage space used by computer systems when maintaining coherency among two or more copies of ordered sets.